package Offer015;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 字符串中的所有变位词
 * @author 23737
 * @time 2021.12.8
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().findAnagrams("abab", "ab"));
        System.out.println(new Solution2().findAnagrams("abab", "ab"));
        System.out.println(new Solution().check("cba", "abc"));
    }
}

/**
 * 思想是对的，但是超时了
 */
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int n = s.length();
        int m = p.length();
        if (n < m) {
            return res;
        }
        for (int i = 0, end = m; end < n + 1; i++, end++) {
//            if(end == n-1) break;
            String str = s.substring(i, end);
            if (check(str, p)) {
                res.add(i);
            }
        }
        return res;
    }

    public boolean check(String s, String p) {
        char[] arrA = s.toCharArray();
        char[] arrB = p.toCharArray();
        Arrays.sort(arrA);
        Arrays.sort(arrB);
        return Arrays.equals(arrA, arrB);
    }
}

class Solution2 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int n = s.length();
        int m = p.length();
        if (m > n) {
            return res;
        }
        int[] arrA = new int[26];
        int[] arrB = new int[26];
        for (int i = 0; i < m; i++) {
            arrA[s.charAt(i) - 'a']++;
            arrB[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(arrA, arrB)) {
            res.add(0);
        }
        for (int i = m; i <= n; i++) {
            arrA[s.charAt(i - 1) - 'a']++;
            arrA[s.charAt(i - m) - 'a']--;
            if (Arrays.equals(arrA, arrB)) {
                res.add(i);
            }
        }
        return res;
    }
}
